LC327. Count of Range Sum
divide and conquer
LC713 Subarray Product Less Than K
Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
可以sliding window，因为特性的增长是单向的
LC992 Subarrays with K Different Integers
Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
LC340 Longest Substring with At Most K Distinct Characters
Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.
LC992和LC159思路类似，都是维护一个sliding window，然后用一个map保存table里面的内容（key -> element, value -> count）
992稍微复杂一些，需要维护两个sliding window，这两个window右边是对齐的，分别表示从左边到右边有K个数字的最大窗口和最小窗口
LC325 Maximum Size Subarray Sum Equals k
对于subarray sum，可以用prefix array的差替代
所以就是一个O(N)+hashmap即可
slding window
LC152. Maximum Product Subarray
是DP
Input: "ABC"
Output: 10
Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC".
Evey substring is composed with only unique letters.
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10
Input: "ABA"
Output: 8
Explanation: The same as example 1, except uni("ABA") = 1.
考虑按照subarray的起点分类
考虑按照每一个元素被几个subarray包含分类（左边界几种可能，右边界几种）
对于每一个字母，边界最远到达字符串结束或者下一个同类字符位置
比如 bdabbabbb，中间的a的左边界最多到第一个a，有3种，右边界到底，最多4种，一共有12个subarray包括了第二个a
LC1055 Shortest Way to Form String
Input: source = "abc", target = "abcbc"
Output: 2
Explanation: The target "abcbc" can be formed by "abc" and "bc", which are subsequences of source "abc".
直接O(N)搜索就行
Sliding Window Maximum的deque解
比如dijkstra的heap，比如Sliding Window Maximum的heap解
比如对于sliding window，或者lazy deletion，每个元素最多添加一次删除一次，所以是O(N*p)，p是每个元素最多的时间复杂度
LC828. Unique Letter String
可以按照subarray的起始点分类，也可以按照每一个元素分类
LC939. Minimum Area Rectangle
可以用对角线两个点来确定一个矩形
LC552. Student Attendance Record II
注意分类，先按照有没有A分类，然后按照长度分类，递推
Input: [3,4,-1,1]
Output: 2
最小的消失的数肯定在1~n范围内，如果一个数i存在，那么一定会在对应的i-1位置上，那么结果一定是对的
反转链表，考虑清楚循环结构
第一是为了确定上界，第二是为了考虑哪里有重复计算（能不能用空间换重复计算？）
比如 LC828. Unique Letter String
找到所有的subarray有O(N^2)，验证每一个subarray有O(N)，所以最坏O(N^3)
想到验证长subarray的时候，也可以顺便验证短的，就可以验证以i点开头的所有subarray的结果，就是O(N^2)
进一步优化，对于每一个i点开头的所有subarray，如果可以比O(N)更快，就可以更好
search tree可以支持add, delete, findmax, find均logN
对于index，
multiset是一个search tree，可以logN维护，并且可以按顺序遍历，但是不能index
对于一个BST，如果维护前面节点的数量，可以O(1)findindex
相比维护sorted array，维护tree更方便，都可以search
如果没有deletion，BST也可以O(1)findindex
用一个map+一个heap，可以实现一种数据结构
add, delete, getmax平均logN
在find sliding window maximum
LC716. Max Stack都可以用
另外的用处是在dijkstra
如果只是一个heap，不支持任意delete
在需要O(1)插入删除的时候可用
在需要存储key-value pair的时候可用，比如对数组建立索引
比如LC716. Max Stack
和sliding window maximum
如果这个集合的插入/删除完全没有规律，可以用heap+lazy deletion，或者search tree
如果有规律，可以事先预存好次优的max
比如sliding window maximum
第一道题是给一个list of schedules, schedule里有[start_time, end_time], 问如果你有一个新的schedule, 是否能塞进去而不重叠
follow up 是现在可以重叠 但是有最大的重叠数限制 一样问能不能放进一个新的schedule而不打破这个限制
楼主写了一个能找出最大重叠数的代码, 以此判断True, False
对于不可能的情况，就是危险区间不足以放下新的schedule
LC621. Task Scheduler
直观怎么解决，算法就是什么
比如对26个字母排序，是O(1)的
两种方法：递归和迭代
LC1096. Brace Expansion II
所以可以考虑sorted/binary search/divide and conquer
对于divide and conquer，只要每次优于O(N^2)就行
LC315. Count of Smaller Numbers After Self
LC493. Reverse Pairs
LC327. Count of Range Sum
如果得出答案分为几步，而且每一步有多种选择，考虑DFS/BFS，进一步优化，可以考虑DP
如果得出答案分为几步，但是可以每一次只选某一个确定的值，考虑greedy
如果可以把问题分成子问题，考虑divide and conquer
对于答案，考虑如何分类解决，比如按照window的起始点分类，按照window的长度分类
如果没有思路，先考虑brute force，然后思考哪里重复计算了